/**
 *  @file MergeDecreasingReuseHead.c
 *  @desc 将两个有序的双向链表合并成一个新的降序链表（复用原链表节点，无需重新创建）
 *  @author WangBlue(wangjiping596@gmail.com)
 *  @date 2025-07-22 17:16
 *  @version 1.0
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// ========================= 结构体定义 =========================

/**
 * @brief 双向链表结点结构体
 */
typedef struct node {
    int data;               ///< 数据域
    struct node *next;      ///< 指向下一个节点
    struct node *pre;       ///< 指向上一个节点
} node, *link;

// ========================= 基础操作函数 =========================

/**
 * @brief 创建一个带数据的新结点
 * @param value 要存储的值
 * @return 成功返回新结点指针，失败返回 NULL
 */
link createNode(int value) {
    link newNode = (link) malloc(sizeof(node));
    if (newNode == NULL) return NULL;
    newNode->next = NULL;
    newNode->pre  = NULL;
    newNode->data = value;
    return newNode;
}

/**
 * @brief 初始化一个带头结点的空链表
 * @param head 指向链表头指针的地址
 */
void initNode(link *head) {
    link newNode = (link) malloc(sizeof(node));
    if (newNode == NULL) return;
    newNode->next = NULL;
    newNode->pre  = NULL;
    newNode->data = 0;  // 头结点不存储有效数据
    *head = newNode;
}

// ========================= 插入操作 =========================

/**
 * @brief 头插法，将新节点插入链表开头（头结点之后）
 * @param head 链表头指针
 * @param value 插入的数据
 */
void istHead(link head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;
    newNode->next = head->next;
    newNode->pre  = head;
    if (head->next != NULL)
        head->next->pre = newNode;
    head->next = newNode;
}

/**
 * @brief 尾插法，将新节点插入链表末尾
 * @param head 链表头指针
 * @param value 插入的数据
 */
void istTail(link head, int value) {
    link cur = head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    link newNode = createNode(value);
    if (newNode == NULL) return;
    cur->next = newNode;
    newNode->pre = cur;
}

// ========================= 打印操作 =========================

/**
 * @brief 从头到尾正向打印链表内容（跳过头结点）
 * @param head 链表头指针
 */
void printList(link head) {
    if (head == NULL || head->next == NULL) return;
    link cur = head->next;
    while (cur != NULL) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

// ========================= 删除与插入位置操作 =========================

/**
 * @brief 删除链表中指定逻辑位置的结点（从 1 开始计数）
 * @param head 链表头指针
 * @param pos 要删除的位置（从 1 开始）
 */
void delByPos(link head, int pos) {
    if (head == NULL || head->next == NULL) return;
    int idx = 1;
    link cur = head->next;
    while (cur != NULL && idx < pos) {
        cur = cur->next;
        idx++;
    }
    if (cur == NULL) return;
    if (cur->pre != NULL)
        cur->pre->next = cur->next;
    if (cur->next != NULL)
        cur->next->pre = cur->pre;
    free(cur);
}

/**
 * @brief 在第 pos 个位置之前插入数据
 * @param head 链表头指针
 * @param value 要插入的值
 * @param pos 插入的位置（从 1 开始）
 */
void insertByPos(link head, int value, int pos) {
    if (head == NULL || pos < 1) return;
    link cur = head;
    int idx = 0;
    while (cur != NULL && idx < pos - 1) {
        cur = cur->next;
        idx++;
    }
    if (cur == NULL) return;
    link newNode = createNode(value);
    if (newNode == NULL) return;
    newNode->next = cur->next;
    newNode->pre  = cur;
    if (cur->next != NULL)
        cur->next->pre = newNode;
    cur->next = newNode;
}

// ========================= 排序判断与翻转 =========================

/**
 * @brief 判断链表是否为降序排列
 * @param head 链表头指针
 * @return 是降序返回 true，否则返回 false
 */
bool isDesc(link head) {
    if (head == NULL || head->next == NULL) return false;
    link cur = head->next;
    if (cur->next != NULL)
        return cur->data > cur->next->data;
    return true; // 只有一个有效节点，也认为是降序
}

/**
 * @brief 原地反转链表（不新建节点）
 * @param head 链表头指针
 */
void reverseList(link head) {
    if (head == NULL || head->next == NULL) return;
    link cur = head->next;
    head->next = NULL;
    while (cur != NULL) {
        link temp = cur->next;
        cur->pre = head;
        cur->next = head->next;
        if (head->next != NULL)
            head->next->pre = cur;
        head->next = cur;
        cur = temp;
    }
}

// ========================= 合并核心逻辑 =========================
/**
 * @brief 合并两个有序链表为一个降序链表（复用原节点）
 *
 * @details
 *  - 支持输入升序或降序链表，函数内部自动判断并转换为降序；
 *  - 所有节点都通过指针重链接，无需重新申请内存；
 *  - 返回的结果链表包含头结点；
 *
 * @param la 指向链表 A 的头结点指针（有序链表，升序或降序）
 * @param lb 指向链表 B 的头结点指针（有序链表，升序或降序）
 * @return 合并后的降序链表头结点指针（含头结点）
 */
link mergeDecreasingReuseHead(link la, link lb) {
    // 如果链表 la 不是降序，则原地翻转
    if (!isDesc(la)) reverseList(la);
    // 如果链表 lb 不是降序，则原地翻转
    if (!isDesc(lb)) reverseList(lb);

    // pa 指向 la 的第一个有效结点（跳过头结点）
    link pa = la->next;
    // pb 指向 lb 的第一个有效结点
    link pb = lb->next;

    // 创建新链表（含头结点）
    link result = NULL;
    initNode(&result);  // 初始化 result 链表头结点
    link tail = result; // tail 指向 result 链表的当前尾部，初始指向头结点

    // 合并两个链表，复用原节点，按降序排列
    while (pa != NULL && pb != NULL) {
        // 比较 pa 和 pb 当前结点的数据
        if (pa->data >= pb->data) {
            // 如果 pa 更大或相等，将 pa 结点接到 result 尾部
            link temp = pa->next;  // 记录下一个节点
            tail->next = pa;       // 当前尾部接上 pa
            pa->pre = tail;        // 设置 pa 的前向指针
            pa->next = NULL;       // 断开 pa 与原链表的连接（后向）
            tail = pa;             // 更新尾部指针
            pa = temp;             // pa 前进
        } else {
            // 同理，如果 pb 更大，将 pb 结点接入
            link temp = pb->next;
            tail->next = pb;
            pb->pre = tail;
            pb->next = NULL;
            tail = pb;
            pb = temp;
        }
    }

    // 如果 pa 还有剩余结点，全部接入 result 尾部
    while (pa) {
        link temp = pa->next;
        tail->next = pa;
        pa->pre = tail;
        pa->next = NULL;
        tail = pa;
        pa = temp;
    }

    // 同理，pb 剩余结点也全部接入 result 尾部
    while (pb) {
        link temp = pb->next;
        tail->next = pb;
        pb->pre = tail;
        pb->next = NULL;
        tail = pb;
        pb = temp;
    }

    return result;  // 返回合并后的降序链表头指针
}

// ========================= 测试主函数 =========================

int main() {
    link head1 = NULL;
    initNode(&head1);
    istTail(head1, 1);
    istTail(head1, 2);
    istTail(head1, 3);

    link head2 = NULL;
    initNode(&head2);
    istTail(head2, 2);
    istTail(head2, 3);
    istTail(head2, 4);

    link result = mergeDecreasingReuseHead(head1, head2);
    printList(result); // 输出: 4, 3, 3, 2, 2, 1
}
